《算法竞赛入门经典》 第2章 循环结构程序设计

发表于 | 分类于

主要讲了for和while两种循环，以及一些需要注意的小细节。

1
2
3
4
5
6
// 输出1到n的值
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n ; i++) {
        printf("%d  ", i);
    }
1
2
3
4
5
6
7
8
9
10
// 2.1 aabb问题
    for (int a = 1; a <= 9; a++) {
        for (int b = 0; b <= 9 ; b++) {
            int n = a * 1100 + b * 11;
            int m = floor(sqrt(n) + 0.5); 
            if (m * m == n) printf("%d \n", n);
        }
    }

7744

解释下floor(sqrt(n) + 0.5)，因为浮点数运算会出现误差，如果结果是0.9999999999，floor后会是0.
因此要四舍五入。

1
2
3
4
5
6
7
8
9
10
11
// 2.1 aabb问题 2
    for (int x = 1; ; x++) {
        int n = x * x;
        if (n < 1000) continue;
        if (n > 9999) break;
        int hi = n / 100;
        int lo = n % 100;
        if (hi / 10 == hi % 10 && lo / 10 == lo % 10) {
            printf("%d\n", n);
        }
    }

if (n < 1000) continue;是为了排除那些不足4位数的n，也可以x直接从32开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 3n + 1问题(错误)
    int n, count = 0;
    scanf("%d", &n);
    while (n > 1) {
        if (n % 2 == 1) n = n * 3 + 1;
        else n /= 2;
        count++;
    }
    printf("%d\n", count);

5
5

// 因为整数是32位的，中间数据会超过int的数值范围
987654321
1
1
2
3
4
5
6
7
8
9
10
11
12
13
// 3n + 1问题
    int n, count = 0;
    scanf("%d", &n);
    long long n2 = n;
    while (n2 > 1) {
        if (n2 % 2 == 1) n2 = n2 * 3 + 1;
        else n2 /= 2;
        count++;
    }
    printf("%d\n", count);

987654321
180

因为不同的编译器，对于long long的scanf“”里的部分是不一样的，所以，在后面引入另外一个临时的长整型，解决问题。

为什么一开始会出现1呢，因为n*3 + 1溢出了。

1
2
3
4
5
6
7
8
9
10
11
// 2.3 近似计算
    double sum = 0;
    for (int i = 0; ; i++) {
        double term = 1.0 / (i * 2 + 1);
        if (i % 2 == 0) sum += term;
        else sum -= term;
        if (term < 1e-6) break;
    }
    printf("%.6f\n", sum);

0.785399
1
2
3
4
5
6
7
8
9
10
11
12
13
// 近似计算do-while版本
    int i = 0;
    double sum = 0;
    double term;
    do {
        term = 1.0 / (i * 2 + 1);
        if (i % 2 == 0) sum += term;
        else sum -= term;
        i++;
    } while (term >= 1e-6);
    printf("%.6f\n", sum);

0.785399
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 阶乘之和
    int n, S = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int factorial = 1;
        for (int j = 1; j <= i; j++) {
            factorial *= j;
        }
        S += factorial;
    }
    printf("%d\n", S % 1000000);

10
37913

100
-961703
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 阶乘之和 2
    const int MOD = 1000000;
    int n, S = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int factorial = 1;
        for (int j = 1; j <= i; j++) {
            factorial = factorial * j % MOD;
            printf("%d %d\t", j, factorial);
        }
        S = (S + factorial) % MOD;
        printf("%d %d %d\n", i, factorial, S);
    }
    printf("%d\n", S);
    printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);

10
1 1     1 1 1
1 1     2 2     2 2 3
1 1     2 2     3 6     3 6 9
1 1     2 2     3 6     4 24    4 24 33
1 1     2 2     3 6     4 24    5 120   5 120 153
1 1     2 2     3 6     4 24    5 120   6 720   6 720 873
1 1     2 2     3 6     4 24    5 120   6 720   7 5040  7 5040 5913
1 1     2 2     3 6     4 24    5 120   6 720   7 5040  8 40320 8 40320 46233
1 1     2 2     3 6     4 24    5 120   6 720   7 5040  8 40320 9 362880        9 362880 409113
1 1     2 2     3 6     4 24    5 120   6 720   7 5040  8 40320 9 362880        10 628800       10 628800 37913
37913

可以看到有大量的重复运算。

（10 + 2） 7 % 5 = 84 % 5 = 4
=（10 % 5 = 0）0 + （2 % 5 = 2）2 7 = 14 % 5 = 4

1
2
3
4
5
6
7
8
9
10
// 数据统计（有bug）
// 输入一些整数,求出它们的最小值,最大值和平均值(保留两位小数)
    int x, n = 0, min, max, s = 0;
    while (scanf("%d", &x) == 1) {
        s += x;
        if (x < min) min = x;
        if (x > max) max = x;
        n++;
    }
    printf("%d %d %.2f\n", min, max, (double)s / n);

min, max 未初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 数据统计（重定向版）
#define LOCAL
#define INF 10000000;

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    
    int x, n = 0;
    int min = INF;
    int max = -INF;
    int s = 0;
    while (scanf("%d", &x) == 1) {
        s += x;
        if (x < min) min = x;
        if (x > max) max = x;
        
//        printf("min = %d, max = %d, s = %d.\n", min, max, s); 
//        用来测试中间变量
        n++;
    }
    printf("%d %d %.2f\n", min, max, (double)s / n);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 数据统计（fopen版）
#define INF 10000000;

    FILE *fin, *fout;
    fin = fopen("data.in", "rb");
    fout = fopen("data.out", "wb");

    int x, n = 0;
    int min = INF;
    int max = -INF;
    int s = 0;
    while (fscanf(fin, "%d", &x) == 1) {
        s += x;
        if (x < min) min = x;
        if (x > max) max = x;
        n++;
    }
    fprintf(fout, "%d %d %.2f\n", min, max, (double)s / n);
    fclose(fin);
    fclose(fout);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 数据统计 II（有Bug）
#define INF 10000000;

    int x, n = 0;
    int min = INF;
    int max = -INF;
    int s = 0;
    int kase = 0;

    while (scanf("%d", &n) == 1 && n) {
        int s = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            s += x;
            if (x < min) min = x;
            if (x > max) max = x;
        }
        if (kase) printf("\n");
        printf("Case %d: %d %d %.2f\n", ++kase, min, max, (double)s / n);
    }
*/
2 8 3 5 1 7 3 6
Case 1: 1 8 4.38
4
-4 6 10 0
Case 2: -4 10 3.00
0

bug在于应该把max和min定义在while里面。

Q：为什么n=0的时候会停止？
A:0几即为false。